home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 18 / CU Amiga Magazine's Super CD-ROM 18 (1997)(EMAP Images)(GB)[!][issue 1998-01].iso / CUCD / Programming / AmigaE / Src / OOmodules / list / doublylinked.e < prev    next >
Encoding:
Text File  |  1995-11-26  |  13.4 KB  |  667 lines
  1. /****** doublylinked/--background-- ******************************************
  2.  
  3.        PURPOSE
  4.          no hassle, flexible, doubly-linked list base class
  5.  
  6.        NOTES
  7.  
  8.           1. head and tail are dummy nodes which are part of the list header.
  9.           They cannot be removed, nor can your data be stored in them!
  10.           Crashes will occur if you attempt to circumvent the methods.  All
  11.           your data nodes are stored AFTER list.head and BEFORE list.tail.
  12.           This is to simplify the algorithms.
  13.  
  14.           2. The following macros are provided for speed and work precisely
  15.           the same as their OO counterparts, except they require the argument
  16.           'list': LISTISEMPTY(list), FIRSTNODE(list), LASTNODE(list).
  17.  
  18.           3. (Gregor Goldbach) Ported the module to the OOEP of the AEE.
  19.           Thus I had to add the methods select(), init() and end(). Made a
  20.           minor change to the dllh object, the attributes are now pointers.
  21.  
  22.           For additional information about modification read the doc of every
  23.           proc.
  24.  
  25.        CREATION
  26.           early September 1995 Gregor Goldbach
  27.  
  28.        HISTORY
  29.           September 10 1995 Gregor Goldbach
  30.             Added length() to dllh.
  31.  
  32. ******************************************************************************
  33.  
  34. History
  35.  
  36.  
  37. */
  38.     new()
  39.       - constructor. ALWAYS call it when NEWing the object!
  40.  
  41.     isEmpty()
  42.       - test if list is empty
  43.  
  44.     firstNode()
  45.       - return first node, list.tail if list is empty
  46.  
  47.     lastNode()
  48.       - return last node, list.head if list is empty
  49.  
  50.     insert(node:PTR TO dlln, listNode:PTR TO dlln)
  51.       - insert node after listnode
  52.  
  53.     addHead(node:PTR TO dlln)
  54.       - add node to front of list
  55.  
  56.     addTail(node:PTR TO dlln)
  57.       - add node to end of list
  58.  
  59.     remove(node:PTR TO dlln)
  60.       - remove node from list, return node
  61.  
  62.     remHead()
  63.       - remove first node from list, return node
  64.  
  65.     remTail()
  66.       - remove last node from list, return node
  67.  
  68.     end()
  69.  
  70.       - automatically called when you END the object. Frees alls resources
  71.         allocated.
  72.  
  73.  
  74. *----------------------------------------------------------------------------*/
  75.  
  76. OPT MODULE
  77. OPT EXPORT,
  78.     REG=5,
  79.     PREPROCESS
  80.  
  81. MODULE 'oomodules/object'
  82.  
  83. OBJECT dlln OF object
  84. /****** dlln/--dlln-- ******************************************
  85.  
  86.        NAME
  87.          dlln -- doubly linked list node
  88.  
  89.        ATTRIBUTES
  90.          pred:PTR TO dlln -- Predecessor
  91.  
  92.          succ:PTR TO dlln -- Successor
  93.  
  94.        SEE ALSO
  95.          doublylinked/--dllh--
  96. ******************************************************************************
  97.  
  98. History
  99.  
  100.  
  101. */
  102.   pred:PTR TO dlln
  103.   succ:PTR TO dlln
  104. ENDOBJECT
  105.  
  106. PROC name() OF dlln IS 'doubly linked list node'
  107. /****** dlln/name ******************************************
  108.  
  109.        NAME
  110.          name() -- Return 'doubly linked list node'
  111.  
  112.        SYNOPSIS
  113.          dlln.name()
  114.  
  115.        FUNCTION
  116.          Returns name of object.
  117.  
  118. ******************************************************************************
  119.  
  120. History
  121.  
  122.  
  123. */
  124. PROC size() OF dlln IS 12
  125. /****** dlln/size ******************************************
  126.  
  127.        NAME
  128.          size() -- Return size of dlln
  129.  
  130.        SYNOPSIS
  131.          dlln.size()
  132.  
  133.        FUNCTION
  134.          Gets you the size of the object.
  135.  
  136. ******************************************************************************
  137.  
  138. History
  139.  
  140.  
  141. */
  142.  
  143. PROC select(optionlist,index) OF dlln
  144. /****** dlln/select ******************************************
  145.  
  146.        NAME
  147.          select() -- Selection of action on initialization
  148.  
  149.        SYNOPSIS
  150.          dlln.select(otionslist,index)
  151.  
  152.        FUNCTION
  153.          Recognizes the following items:
  154.            "pred" -- next item is predecessor
  155.  
  156.            "succ" -- next item is successor
  157.  
  158.        INPUTS
  159.          optionlist -- optionlist
  160.  
  161.          index -- index of optionlist
  162.  
  163.        SEE ALSO
  164.          object/select()
  165. ******************************************************************************
  166.  
  167. History
  168.  
  169.  
  170. */
  171. ->  TODO: error check: len-o'-list!
  172. DEF item, value
  173.  
  174.   item := ListItem(optionlist, index)
  175.  
  176.   SELECT item
  177.     CASE "pred"
  178.       INC index
  179.       self.pred := ListItem(optionlist,index)
  180.  
  181.     CASE "succ"
  182.       INC index
  183.       self.succ := ListItem(optionlist,index)
  184.  
  185.   ENDSELECT
  186.  
  187. ENDPROC index
  188.  
  189. OBJECT dllh OF object
  190. /****** dllh/--dllh-- ******************************************
  191.  
  192.        NAME
  193.          dllh -- doubly linked list header
  194.  
  195.        ATTRIBUTES
  196.          head:PTR TO dlln -- The head of the list
  197.  
  198.          tail:PTR TO dlln -- The tail of the list
  199.  
  200.        SEE ALSO
  201.          doublylinked/--dlln--
  202. ******************************************************************************
  203.  
  204. History
  205.  
  206.  
  207. */
  208.   head:PTR TO dlln
  209.   tail:PTR TO dlln
  210. ENDOBJECT
  211.  
  212. PROC name() OF dllh IS 'doubly linked list header'
  213. /****** dllh/name ******************************************
  214.  
  215.        NAME
  216.          name() -- Return 'doubly linked list header'
  217.  
  218.        SYNOPSIS
  219.          dllh.name()
  220.  
  221.        FUNCTION
  222.          Returns the name of the object.
  223.  
  224. ******************************************************************************
  225.  
  226. History
  227.  
  228.  
  229. */
  230. PROC size() OF dllh IS 28 ->12+12+4
  231. /****** dllh/size ******************************************
  232.  
  233.        NAME
  234.          size() -- Get size of object
  235.  
  236.        SYNOPSIS
  237.          dllh.size()
  238.  
  239.        FUNCTION
  240.          Gets you the size of the object.
  241.  
  242. ******************************************************************************
  243.  
  244. History
  245.  
  246.  
  247. */
  248.  
  249. PROC select(optionlist,index) OF dllh
  250. /****** dllh/select ******************************************
  251.  
  252.        NAME
  253.          select() -- Select actionon initialization.
  254.  
  255.        SYNOPSIS
  256.          dllh.select()
  257.  
  258.        FUNCTION
  259.          Recognizes no items.
  260.  
  261. ******************************************************************************
  262.  
  263. History
  264.  
  265.  
  266. */
  267. ->  TODO: error check: len-o'-list!
  268. DEF item, value
  269.  
  270. ->  item := ListItem(optionlist, index)
  271.  
  272. ENDPROC index
  273.  
  274. PROC init() OF dllh
  275. /****** dllh/init ******************************************
  276.  
  277.        NAME
  278.          init() -- Initialization of object.
  279.  
  280.        SYNOPSIS
  281.          dllh.init()
  282.  
  283.        FUNCTION
  284.          Initializes the object that way that an empty list is created.
  285. ******************************************************************************
  286.  
  287. History
  288.  
  289.  
  290. */
  291. DEF n:PTR TO dlln
  292.  
  293.   NEW n.new()
  294.   self.head := n
  295.  
  296.   NEW n.new()
  297.   self.tail := n
  298.  
  299.   self.head.succ:=self.tail
  300.   self.tail.pred:=self.head
  301.   self.head.pred:=NIL
  302.   self.tail.succ:=NIL
  303. ENDPROC
  304.  
  305. PROC end() OF dllh
  306. /****** dllh/end ******************************************
  307.  
  308.        NAME
  309.          end() -- Global destructor.
  310.  
  311.        SYNOPSIS
  312.          dllh.end()
  313.  
  314.        FUNCTION
  315.          Frees allocated resources. This does NOT mean that the list is
  316.          automatically cleared.
  317.  
  318. ******************************************************************************
  319.  
  320. History
  321.  
  322.  
  323. */
  324. DEF n
  325.  
  326.   n := self.tail
  327.   Dispose(n)
  328.  
  329.   n := self.head
  330.   Dispose(n)
  331.  
  332. ENDPROC
  333.  
  334.  
  335. #define LISTISEMPTY(list) (list::dllh.head.succ=list::dllh.tail)
  336. /****** dllh/LISTISEMPTY ******************************************
  337.  
  338.        NAME
  339.          LISTISEMPTY
  340.  
  341.        SYNOPSIS
  342.          LISTISEMPTY(list:PTR TO dllh)
  343.  
  344.        FUNCTION
  345.          Test if the list is empty.
  346.  
  347.        INPUTS
  348.          list:PTR TO dllh -- The list to test
  349.  
  350.        RESULT
  351.          TRUE if the list is empty, FALSE otherwise
  352.  
  353. ******************************************************************************
  354.  
  355. History
  356.  
  357.  
  358. */
  359. #define FIRSTNODE(list)   (list::dllh.head.succ)
  360. /****** dllh/FIRSTNODE ******************************************
  361.  
  362.        NAME
  363.          FIRSTNODE -- Get first node of list.
  364.  
  365.        SYNOPSIS
  366.          FIRSTNODE(list:PTR TO dllh)
  367.  
  368.        FUNCTION
  369.          Get the first node of the list.
  370.  
  371.        INPUTS
  372.          list:PTR TO dllh -- The list to get the first node of.
  373.  
  374.        RESULT
  375.          PTR TO dlln -- The first node of the list
  376.  
  377. ******************************************************************************
  378.  
  379. History
  380.  
  381.  
  382. */
  383. #define LASTNODE(list)    (list::dllh.tail.pred)
  384. /****** dllh/LASTNODE ******************************************
  385.  
  386.        NAME
  387.          LASTNODE -- Get first node of list.
  388.  
  389.        SYNOPSIS
  390.          LASTNODE(list:PTR TO dllh)
  391.  
  392.        FUNCTION
  393.          Get the last node of the list.
  394.  
  395.        INPUTS
  396.          list:PTR TO dllh -- The list to get the last node of.
  397.  
  398.        RESULT
  399.          PTR TO dlln -- The last node of the list
  400.  
  401. ******************************************************************************
  402.  
  403. History
  404.  
  405.  
  406. */
  407.  
  408. PROC isEmpty() OF dllh   IS self.head.succ=self.tail
  409. /****** dllh/isEmpty ******************************************
  410.  
  411.        NAME
  412.          isEmpty() -- Is the list empty?
  413.  
  414.        SYNOPSIS
  415.          dllh.isEmpty()
  416.  
  417.        FUNCTION
  418.          Test if the list is empty.
  419.  
  420.        RESULT
  421.          TRUE if the list is empty, FALSE otherwise
  422.  
  423. ******************************************************************************
  424.  
  425. History
  426.  
  427.  
  428. */
  429. PROC firstNode() OF dllh IS self.head.succ
  430. /****** dllh/firstNode ******************************************
  431.  
  432.        NAME
  433.          firstNode() -- Get first node of list.
  434.  
  435.        SYNOPSIS
  436.          dllh.firstNode()
  437.  
  438.        FUNCTION
  439.          Get the first node of the list.
  440.  
  441.        RESULT
  442.          PTR TO dlln -- The first node of the list
  443.  
  444. ******************************************************************************
  445.  
  446. History
  447.  
  448.  
  449. */
  450. PROC lastNode() OF dllh  IS self.tail.pred
  451. /****** dllh/lastNode ******************************************
  452.  
  453.        NAME
  454.          lastNode() -- Get first node of list.
  455.  
  456.        SYNOPSIS
  457.          dllh.lastNode()
  458.  
  459.        FUNCTION
  460.          Get the last node of the list.
  461.  
  462.        RESULT
  463.          PTR TO dlln -- The last node of the list
  464.  
  465. ******************************************************************************
  466.  
  467. History
  468.  
  469.  
  470. */
  471.  
  472. PROC insert(node:PTR TO dlln, listNode:PTR TO dlln) OF dllh
  473. /****** dllh/insert ******************************************
  474.  
  475.        NAME
  476.          insert() -- Insert node in list.
  477.  
  478.        SYNOPSIS
  479.          dllh.insert(node:PTR TO dlln, listNode:PTR TO dlln)
  480.  
  481.        FUNCTION
  482.          Inserts a node after another.
  483.  
  484.        INPUTS
  485.          node:PTR TO dlln -- Node to insert.
  486.  
  487.          listNode:PTR TO dlln -- Node after which the first node will be
  488.              inserted.
  489.  
  490. ******************************************************************************
  491.  
  492. History
  493.  
  494.  
  495. */
  496.   node.pred:=listNode
  497.   node.succ:=listNode.succ
  498.   listNode.succ:=node
  499.   listNode:=node.succ
  500.   listNode.pred:=node
  501. ENDPROC
  502.  
  503. PROC addHead(node:PTR TO dlln) OF dllh
  504. /****** dllh/addHead ******************************************
  505.  
  506.        NAME
  507.          addHead() -- Insert node at the head of the list.
  508.  
  509.        SYNOPSIS
  510.          dllh.addHead(node:PTR TO dlln)
  511.  
  512.        FUNCTION
  513.          Inserts a node at the head of the list.
  514.  
  515.        INPUTS
  516.          node:PTR TO dlln -- Node to insert.
  517.  
  518. ******************************************************************************
  519.  
  520. History
  521.  
  522.  
  523. */
  524.   self.insert(node, self.head)
  525. ENDPROC
  526.  
  527. PROC addTail(node:PTR TO dlln) OF dllh
  528. /****** dllh/addTail ******************************************
  529.  
  530.        NAME
  531.          addTail() -- Insert a node at the tail of the list.
  532.  
  533.        SYNOPSIS
  534.          dllh.addTail(node:PTR TO dlln)
  535.  
  536.        FUNCTION
  537.          Inserts a node at the tail of the list.
  538.  
  539.        INPUTS
  540.          node:PTR TO dlln -- Node to insert.
  541.  
  542. ******************************************************************************
  543.  
  544. History
  545.  
  546.  
  547. */
  548.   self.insert(node, self.tail.pred)
  549. ENDPROC
  550.  
  551. PROC remove(node:PTR TO dlln) OF dllh
  552. /****** dllh/remove ******************************************
  553.  
  554.        NAME
  555.          remove() -- Removes a node from the list.
  556.  
  557.        SYNOPSIS
  558.          dllh.remove(node:PTR TO dlln)
  559.  
  560.        FUNCTION
  561.          Removes a node from the list it's in.
  562.  
  563.        INPUTS
  564.          node:PTR TO dlln -- Node to remove.
  565.  
  566.        RESULT
  567.          PTR TO dlln -- The node that was removed.
  568.  
  569. ******************************************************************************
  570.  
  571. History
  572.  
  573.  
  574. */
  575.   IF self.head.succ=self.tail THEN RETURN NIL
  576.   node.pred.succ:=node.succ
  577.   node.succ.pred:=node.pred
  578.   node.succ:=NIL
  579.   node.pred:=NIL
  580. ENDPROC node
  581.  
  582. PROC remHead() OF dllh IS self.remove(self.head.succ)
  583. /****** dllh/remHead ******************************************
  584.  
  585.        NAME
  586.          remHead() -- Remove the head of the list.
  587.  
  588.        SYNOPSIS
  589.          dllh.remHead()
  590.  
  591.        FUNCTION
  592.          Removes it's head.
  593.  
  594.        RESULTS
  595.          PTR TO dlln -- The ex-head.
  596.  
  597. ******************************************************************************
  598.  
  599. History
  600.  
  601.  
  602. */
  603.  
  604. PROC remTail() OF dllh IS self.remove(self.tail.succ)
  605. /****** dllh/remTail ******************************************
  606.  
  607.        NAME
  608.          remTail() -- Remove the tail of the list.
  609.  
  610.        SYNOPSIS
  611.          dllh.remTail()
  612.  
  613.        FUNCTION
  614.          Removes it's tail.
  615.  
  616.        RESULT
  617.          PTR TO dlln -- The ex-tail.
  618.  
  619. ******************************************************************************
  620.  
  621. History
  622.  
  623.  
  624. */
  625.  
  626. PROC length() OF dllh
  627. /****** dllh/length ******************************************
  628.  
  629.        NAME
  630.          length() -- Get the length of the list.
  631.  
  632.        SYNOPSIS
  633.          dllh.length()
  634.  
  635.        FUNCTION
  636.          Gets the number of nodes in this list. 0 means the list is empty.
  637.  
  638.        RESULT
  639.          The number of nodes in this list.
  640.  
  641. ******************************************************************************
  642.  
  643. History
  644.  
  645.  
  646. */
  647. DEF actualNode:PTR TO dlln,
  648.     lastNode:PTR TO dlln,
  649.     count=1
  650.  
  651.   IF self.isEmpty() THEN RETURN 0
  652.  
  653.   actualNode := self.firstNode()
  654.   lastNode := self.lastNode()
  655.  
  656.  
  657.   WHILE (actualNode<>lastNode)
  658.     actualNode := actualNode.succ
  659.     count++
  660.   ENDWHILE
  661.  
  662. ENDPROC count
  663. /*EE folds
  664. -1
  665. 83 21 122 43 125 21 164 22 167 28 170 26 311 28 314 21 317 21 320 28 367 35 
  666. EE folds*/
  667.